/*
Date:20210509 14:45PM
key:0级台阶一种跳法哦，所以是n+1的大小
*/
class Solution {
public:
    int numWays(int n) {
        int*dp=new int[n+1];
        for(int i=0;i<n+1;i++)
        {
            if(i==0){dp[i]=1;continue;}
            if(i==1){dp[i]=1;continue;}
            if(i==2){dp[i]=2;}
            else{dp[i]=(dp[i-1]+dp[i-2])%(1000000007);}
            
        }
        return dp[n];
    }
};